package week02

import "fmt"

// 22. 括号生成
// https://leetcode-cn.com/problems/generate-parentheses/

func generateParenthesis(n int) []string {
	return generateParenthesis2(n, make(map[int][]string))
}

func generateParenthesis2(n int, record map[int][]string) []string {
	if n == 0 {
		return []string{""}
	}
	if v, ok := record[n]; ok {
		return v
	}
	// (a)b
	// (a) k个
	// b n-k个
	var ans []string
	// (a) 至少有1个
	for k := 1; k <= n; k++ {
		var ans_a = generateParenthesis2(k-1, record)
		var ans_b = generateParenthesis2(n-k, record)
		for _, a := range ans_a {
			for _, b := range ans_b {
				ans = append(ans, fmt.Sprintf("(%s)%s", a, b))
			}
		}
	}
	record[n] = ans
	return ans
}